//Given an array of integers heights representing the histogram's bar height whe
//re the width of each bar is 1, return the area of the largest rectangle in the h
//istogram. 
//
// 
// Example 1: 
//
// 
//Input: heights = [2,1,5,6,2,3]
//Output: 10
//Explanation: The above is a histogram where width of each bar is 1.
//The largest rectangle is shown in the red area, which has an area = 10 units.
// 
//
// Example 2: 
//
// 
//Input: heights = [2,4]
//Output: 4
// 
//
// 
// Constraints: 
//
// 
// 1 <= heights.length <= 105 
// 0 <= heights[i] <= 104 
// 
// Related Topics 栈 数组 
// 👍 1329 👎 0


package leetcode.editor.cn;

import java.util.Stack;

//Java：Largest Rectangle in Histogram
 class P84LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new P84LargestRectangleInHistogram().new Solution();
        // TO TEST
        System.out.println(solution.largestRectangleArea(new int[]{2, 4}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int largestRectangleArea(int heights[]) {
            Stack<Integer> stack = new Stack<>();
            int[] arr = new int[heights.length + 2];
            System.arraycopy(heights, 0, arr, 1, heights.length);
            int area = 0;
            for (int i = 0; i < arr.length; i++) {
                while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
                    int h = arr[stack.pop()];
                    area = Math.max(area, (i - stack.peek() - 1) * h);
                }
                stack.push(i);
            }
            return area;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}